﻿using System;
using System.Runtime.InteropServices;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Collections.Specialized;
using System.Runtime.CompilerServices;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using System.Threading;
using System.Windows.Markup;

using alib.Character;
using alib.Debugging;
using alib.Enumerable;
using alib.Reflection;
using alib.Dictionary;

namespace alib.Hashing
{
	using String = System.String;

	public interface IIndexedHash<T> : _IList<T>
	{
		int this[T to_find] { get; }
		T[] ConvertTo(IEnumerable<int> items);
		int[] ConvertFrom(IEnumerable<T> items);
	};

	/// <summary>
	/// A distinct set where a unique, contiguous, 0-based index is provided for each item 
	/// and O(1) access is provided for both item-to-index and index-to-item lookup. Most importantly,
	/// each index value is permanent; index values do not change across internal resizing operations.
	/// Cannot delete items once added.
	/// </summary>
	[DebuggerDisplay("Count={Count}")]
	public class IndexedHash<T> : IIndexedHash<T>, IAddRangeColl<T>
	{
		const int MinCapacity = 17;

		protected IndexedHash(int capacity, int hash_size, IEqualityComparer<T> cmp)
		{
			if (capacity <= 0)
				capacity = MinCapacity;
			if (hash_size < capacity)
				hash_size = capacity;
			this.cmp = cmp ?? EqualityComparer<T>.Default;
			this.items_arr = new T[capacity];
			this.i_next = 0;
			this.rgrgh = new int[hash_size][];
		}

		public IndexedHash(int capacity)
			: this(capacity = capacity < MinCapacity ? MinCapacity : capacity, alib.Math.Primes.HashFriendly(capacity), default(IEqualityComparer<T>))
		{
		}

		public IndexedHash(IEnumerable<T> items_in)
			: this(items_in._Count())
		{
			var e = items_in.GetEnumerator();
			while (e.MoveNext())
				Add(e.Current);
		}

		public IndexedHash()
			: this(MinCapacity)
		{
		}

		protected int i_next;
		protected T[] items_arr;
		protected int[][] rgrgh;
		public IEqualityComparer<T> cmp;

		/// <summary> Note: may have excess length </summary>
		public T[] GetItemsArray() { return items_arr; }

		public T this[int index] { get { return items_arr[index]; } }

		public bool Contains(T s) { return this[s] != -1; }

		public int Count { get { return i_next; } }

		public int Capacity { get { return items_arr.Length; } }

		public int this[T to_find]
		{
			get
			{
				uint h;
				return find(to_find, out h);
			}
		}

		void ICollection<T>.Add(T item) { this.Add(item); }

#if DEBUG
		static int thread_check;
#endif

		/// <summary>
		/// To determine if the item was added, save the value of 'Count' prior to calling this
		/// </summary>
		public virtual int Add(T item)
		{
#if DEBUG
			if (++thread_check != 1)
				throw new Exception("Need thread safety");
#endif
			uint h;
			int ix;
			if ((ix = find(item, out h)) == -1)
			{
				if (i_next == items_arr.Length)
				{
					resize();
					h = (uint)cmp.GetHashCode(item) % (uint)rgrgh.Length;
				}

				items_arr[ix = i_next++] = item;
				alib.Array.arr.Append(ref rgrgh[h], ix);
			}
#if DEBUG
			thread_check--;
#endif
			return ix;
		}

		/// <summary>
		/// Not thread safe
		/// </summary>
		public int Add(T item, out bool f_added)
		{
			uint h;
			int ix;
			if (f_added = (ix = find(item, out h)) == -1)
			{
				if (i_next == items_arr.Length)
				{
					resize();
					h = (uint)cmp.GetHashCode(item) % (uint)rgrgh.Length;
				}

				items_arr[ix = i_next++] = item;
				alib.Array.arr.Append(ref rgrgh[h], ix);
			}
			return ix;
		}

		public void AddRange(IEnumerable<T> rg)
		{
			var e = rg.GetEnumerator();
			while (e.MoveNext())
				Add(e.Current);
		}

		int find(T item, out uint h)
		{
			var rgh = rgrgh[h = (uint)cmp.GetHashCode(item) % (uint)rgrgh.Length];
			if (rgh != null)
				for (int ix, i = rgh.Length - 1; i >= 0; i--)
					if (cmp.Equals(items_arr[ix = rgh[i]], item))
						return ix;
			return -1;
		}

		void resize()
		{
			Debug.Assert(i_next == items_arr.Length);

			var _new = new T[i_next << 1];
			var d = Math.Primes.HashFriendly(_new.Length);
			this.rgrgh = new int[d][];

			for (int i = 0; i < i_next; i++)
				alib.Array.arr.Append(ref rgrgh[(uint)cmp.GetHashCode(_new[i] = items_arr[i]) % (uint)d], i);

			this.items_arr = _new;
		}

		public void TrimExcess()
		{
			this.items_arr = alib.Array.arr.Resize(items_arr, i_next);
		}

		public T[] ToArray()
		{
			var c = i_next;
			return alib.Array.arr.Resize(items_arr, c);
		}

		public T[] ConvertTo(IEnumerable<int> items)
		{
			T[] arr = new T[items._Count()];
			int i = 0;
			var e = items.GetEnumerator();
			while (e.MoveNext())
				arr[i++] = this[e.Current];
			return arr;
		}

		public int[] ConvertFrom(IEnumerable<T> items)
		{
			int[] arr = new int[items._Count()];
			int i = 0;
			var e = items.GetEnumerator();
			while (e.MoveNext())
				arr[i++] = this[e.Current];
			return arr;
		}

		public void CopyTo(T[] array, int index)
		{
			for (int i = 0; i < i_next; i++)
				array[index++] = items_arr[i];
		}

		public void CopyTo(System.Array array, int index)
		{
			for (int i = 0; i < i_next; i++)
				array.SetValue(items_arr[i], index++);
		}

		public IEnumerator<T> GetEnumerator()
		{
			for (int i = 0; i < i_next; i++)
				yield return items_arr[i];
		}

		IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }

		public bool IsReadOnly { get { return false; } }
		public bool IsSynchronized { get { return false; } }
		public bool Remove(T item) { throw not.valid; }
		public void Clear() { throw not.valid; }
		public Object SyncRoot { get { return this; } }
	};

	/// <summary>
	/// A distinct set where a unique, contiguous, 0-based index is provided for each item 
	/// and O(1) access is provided for both item-to-index and index-to-item lookup. Most importantly,
	/// each index value is permanent; index values do not change across internal resizing operations.
	/// Cannot delete items once added.
	/// </summary>
	public class IndexedHashSafe<T> : IReadOnlyList<T>
		where T : class
	{
		public IndexedHashSafe(int capacity = 0)
		{
			if (capacity <= 0)
				capacity = 37;
			data = new ih(capacity);
		}

		public IndexedHashSafe(IEnumerable<T> items_in)
			: this(items_in._Count())
		{
			var e = items_in.GetEnumerator();
			while (e.MoveNext())
				Add(e.Current);
		}

		ih data;

		public T this[int index] { get { return data.get(index); } }

		public int this[T to_find] { get { return data.find(to_find); } }

		public int Count { get { return data.i_next; } }

		public int Add(T item)
		{
			int i;
			var _tmp = data;
			while (_tmp != (_tmp = _tmp.add(ref data, item, out i)))
				;
			return i;
		}

		sealed class ih
		{
			public ih(int c_size)
			{
				this.items_arr = new T[c_size];
				this.rgrgh = new int[Math.Primes.HashFriendly(c_size)][];
				this.i_next = 0;
			}
			ih(ih _prv)
				: this(_prv.items_arr.Length * 2)
			{
				var _arr = _prv.items_arr;
				this.i_next = _arr.Length;

				int c, d = rgrgh.Length;
				int[] src, dst;
				for (int i = 0; i < i_next; i++)
				{
					uint j = (uint)(items_arr[i] = _arr[i]).GetHashCode() % (uint)d;
					if ((src = rgrgh[j]) == null)
						rgrgh[j] = new[] { i };
					else
					{
						(rgrgh[j] = dst = new int[(c = src.Length) + 1])[c] = i;
						while (--c >= 0)
							dst[c] = src[c];
					}
				}
			}
			public int i_next;
			public readonly T[] items_arr;
			public readonly int[][] rgrgh;

			public T get(int index) { return items_arr[index]; }

			public int find(T item, out uint h)
			{
				var rgh = rgrgh[h = (uint)item.GetHashCode() % (uint)rgrgh.Length];
				if (rgh != null)
					for (int ix, i = rgh.Length - 1; i >= 0; i--)
						if (items_arr[ix = rgh[i]].Equals(item))
							return ix;
				return -1;
			}
			public int find(T item)
			{
				uint h;
				return find(item, out h);
			}
			public ih add(ref ih _target, T item, out int ix)
			{
				while (true)
				{
					uint h;
					if ((ix = find(item, out h)) != -1)
						return this;

					if ((ix = i_next) == items_arr.Length)
					{
						ih _tmp, _new = new ih(this);
						if ((_tmp = _target) != this)
							return _tmp;

						return this == (_tmp = Interlocked.CompareExchange(ref _target, _new, this)) ? _new : _tmp;
					}
					if (null == Interlocked.CompareExchange(ref items_arr[ix], item, null))
					{
						alib.Array.arr.AppendSafe(ref rgrgh[h], ix);
						if (ix == Interlocked.CompareExchange(ref i_next, ix + 1, ix))
							return this;
					}
				}
			}

			public IEnumerator<T> GetEnumerator()
			{
				for (int i = 0; i < i_next; i++)
					yield return items_arr[i];
			}
		}

		public IEnumerator<T> GetEnumerator() { return data.GetEnumerator(); }

		IEnumerator IEnumerable.GetEnumerator() { return data.GetEnumerator(); }
	};


	public class NotifyingIndexedHash<T> : IndexedHash<T>, INotifyCollectionChanged
	{
		protected NotifyingIndexedHash(int capacity, int hash_size)
			: base(capacity, hash_size, default(IEqualityComparer<T>))
		{
		}

		public NotifyingIndexedHash(int capacity)
			: base(capacity)
		{
		}

		public NotifyingIndexedHash(IEnumerable<T> items_in)
			: base(items_in)
		{
		}

		public NotifyingIndexedHash()
			: base()
		{
		}

		public sealed override int Add(T item)
		{
			int i = base.Add(item);
			var _tmp = CollectionChanged;
			if (_tmp != null)
				_tmp(this, new NotifyCollectionChangedEventArgs(NotifyCollectionChangedAction.Add, (Object)item));
			return i;
		}

		public event NotifyCollectionChangedEventHandler CollectionChanged;
	};

	[DebuggerDisplay("Count={Count}")]
	public class StringIndex : IndexedHash<String>
	{
		protected StringIndex(int capacity, int hash_size, IEqualityComparer<String> cmp)
			: base(capacity, hash_size, cmp)
		{
		}
		public StringIndex(int capacity)
			: base(capacity)
		{
		}
		public StringIndex(ICollection<String> items_in)
			: base(items_in)
		{
		}
		public StringIndex()
		{
		}
		public StringIndex(StringComparison comparison_type)
			: base(0, 0, alib.String._string_ext.GetComparer(comparison_type))
		{
		}

		public void Write(alib.IO._BinaryWriter bw)
		{
			int c = items_arr.Length;
			bw.Write(c);

			int ch = rgrgh.Length;
			bw.Write(ch);

			bw.Write(i_next);

			for (int i = 0; i < i_next; i++)
				bw.Write(items_arr[i]);

			for (int i = 0; i < ch; i++)
			{
				var rgh = rgrgh[i];
				int cc = rgh == null ? 0 : rgh.Length;
				bw.Write7BitEncodedInt(cc);
				for (int j = 0; j < cc; j++)
					bw.Write7BitEncodedInt(rgh[j]);
			}
		}

		public static StringIndex Read(alib.IO._BinaryReader br)
		{
			int c = br.ReadInt32();

			int ch = br.ReadInt32();

			var s = new StringIndex(c, ch, default(IEqualityComparer<String>));

			s.i_next = br.ReadInt32();

			for (int i = 0; i < s.i_next; i++)
				s.items_arr[i] = br.ReadString();

			for (int i = 0; i < ch; i++)
			{
				int cc = br.Read7BitEncodedInt();
				if (cc > 0)
				{
					var rgh = s.rgrgh[i] = new int[cc];
					for (int j = 0; j < cc; j++)
						rgh[j] = br.Read7BitEncodedInt();
				}
			}
			return s;
		}
	};
}
